\chapter{BArbre}

\section{Analyse}
\subsection{Définition}
\begin{figure}
  \center
   \includegraphics[scale=0.5]{BARBRE}
  \caption{Exemple de B-arbre}
\end{figure}
   un arbre B est une structure de données permettant de gérer un arbre constamment équilibré. A chaque modification du contenu de l'arbre, celui-ci est autmatiquement trié.
Le principe général est de permettre aux nœuds de posséder plus d'une clé ; cela permet de minimiser la hauteur de l'arbre. De plus un B-arbre grandit à partir de la racine, contrairement à l'arbre binaire qui est extensible à partir des feuilles. 

\subsection{Ressource}
N'ayant aucune connaissance préalable sur la structure de BArbre, il a été nécessaire de rechercher des informations sur des sources externes. A cet effet, la documentation de l'Institut National des Sciences Appliquées à Rouen au Département Architecture des Systèmes d’Information s'est montré très utile concernant la compréhension des barbres.

Il fut nécessaire de se poser la question de la récupération des valeurs dans l'ordre à l'intérieur de chaque noeud. Il fut décidé de considérer une structure PNode contenant une valeur et un pointeur sur l'eventuelle branche de gauche. Un noeud est ainsi consititué de pNode, la dernière branche étant gérée par un stub de PNode situé à la fin du vecteur de PNode ayant la valeur de la clé à null.

\section{Structure du programme}

\subsection{Structure annexe}
\begin{itemize}
\renewcommand{\labelitemi}{$\triangleright$}
\item PNode : Structure annexe représentant les éléments contenus du Barbre. Cette structure permet ainsi de récupérer la valeur d'un élément ainsi que le pointeur situé à la gauche de cet élément.
\item Node : Structure annexe représentant les noeuds du Barbres. Nous avons ainsi accès à un vecteur de PNode ainsi qu'au parent de ce noeud.
\item NodeIT : Structure annexe permettant de gérer efficacement l'accès à un Pnode en fournissant un noeud ainsi que l'iterateur corespondant au pNode souhaité.
\item Iterator : Cet itérateur permet de rechercher les valeurs de l'arbre via un parcours en profondeur. Les valeurs retournées sont celles des éléments des Pnodes selon leur agencement de gauche à droite dans le noeud. une fois un noeud entièrement parcouru, le premier pointeur renvoie 
\end{itemize}


\subsection{Structure principale}

La structure Barbres permet d'insérer des valeurs dans les structures d'éléments (PNode), elle-mêmes incluses dans les structures de noeud (Node). L' arbre étant équilibré a chaque opération, les noeuds sont automatiquement insérés.
Le programme BArbres est ainsi constitué des éléments privés suivants:
\begin{itemize}
\renewcommand{\labelitemi}{$\triangleright$}
\item une méthode de comparaison des noeuds
\item une méthode de recherche
\end{itemize}

l'utilisateur dispose des éléments suivant:
\begin{itemize}
\renewcommand{\labelitemi}{$\triangleright$}
\item une méthode d'insertion
\item une méthode de suppression
\item un iterateur
\end{itemize}
\section{Jeux d'essais}
le jeu de test correspondant au BArbres contenant les valeurs "1,2,3,4,5,9,12" fonctionne correctement
